package leetcode.code0877;

public class Solution extends Solution877 {

	@Override
	public boolean stoneGame(int[] piles) {
		int len = piles.length;
		int[][] f = new int[len + 1][len + 1];
		int[][] s = new int[len + 1][len + 1];
		for (int i = 0; i < len; i++) {
			f[i + 1][i + 1] = piles[i];
		}
		for (int l = len - 1; l >= 0; l--) {
			for (int r = l + 1; r < len; r++) {
				// 此轮中先手
				int max = piles[l] + s[l + 1][r];// 拿左边的,[l+1,r]作为后手
				max = Math.max(max, piles[r] + s[l][r - 1]);// 拿右边的,[l,r-1]作为后手
				f[l][r] = max;// 我可以选择其中最大的
				// 此轮中后手
				int min = f[l + 1][r];// 如果先手拿左边的,[l+1,r]作为先手
				min = Math.min(min, f[l][r - l]);// 如果先手拿右边的,[l,r-1]作为先手
				s[l][r] = min;// 我只能被动选择其中最小的
			}
		}
		return f[0][len - 1] > s[0][len - 1];// 先手能拿到的结果比后手大,则先手胜利
//		return f(piles, 0, piles.length - 1) > s(piles, 0, piles.length - 1);
	}

	public int f(int[] piles, int l, int r) {
		if (l == r)
			return piles[l];
		int max = piles[l] + s(piles, l + 1, r);
		max = Math.max(max, piles[r] + s(piles, l, r - 1));
		return max;
	}

	public int s(int[] piles, int l, int r) {
		if (l == r)
			return 0;
		int min = f(piles, l + 1, r);
		min = Math.min(min, f(piles, l, r - 1));
		return min;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
	}

}
